// https://www.lintcode.com/problem/heaters/

public class Solution {
    /**
     * @param houses: positions of houses
     * @param heaters: positions of heaters
     * @return: the minimum radius standard of heaters
     */
    public int findRadius(int[] houses, int[] heaters) {
        // Write your code here
        int ret = 0;
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int j = 0;
        for (int i = 0; i < houses.length; ++i) {
            while (j < (heaters.length - 1)) {
                int diff_1 = Math.abs(heaters[j] - houses[i]);
                int diff_2 = Math.abs(heaters[j + 1] - houses[i]);
                if (diff_1 >= diff_2) {
                    ++j;
                } else {
                    break;
                }
            }
            ret = Math.max(ret, Math.abs(heaters[j] - houses[i]));
        }
        return ret;
    }
}